import java.util.*;

/**
 * Created by L.jp
 * Description:给定一个二叉树，返回该二叉树的之字形层序遍历，
 * （第一层从左向右，下一层从右向左，一直这样交替）
 * User: 86189
 * Date: 2022-06-02
 * Time: 23:49
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
        this.val = val;
        
    }
    
}
/**
 * @author 86189
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        TreeNode cur=pRoot;
        ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
        if(cur == null){
            return ret;
        }
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add( cur);
        //第一层
        boolean flag=true;
        while ( !queue.isEmpty() ){
            int size=queue.size();
            //存放每一层的节点
            ArrayList<Integer> tmp=new ArrayList<>();
            //每到新的一层就要更新，起始标志为false,也就是第一层
            flag=!flag;
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                tmp.add( node.val );
                //如果还有左右子节点就加入
                if(node.left!=null){
                    queue.add( node.left );
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            //奇数行不翻转偶数行翻转
            if(flag){
                Collections.reverse( tmp );
            }
            ret.add( tmp );
        }
        return ret;
    }
}
